home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1994 November / macformat-018.iso / Utility Spectacular / Developer / Marlais 0.3.1 / gc4.1-mac / cord / cord.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-26  |  12.7 KB  |  298 lines  |  [TEXT/R*ch]
  1. /* 
  2.  * Copyright (c) 1993-1994 by Xerox Corporation.  All rights reserved.
  3.  *
  4.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  5.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  6.  *
  7.  * Permission is hereby granted to use or copy this program
  8.  * for any purpose,  provided the above notices are retained on all copies.
  9.  * Permission to modify the code and to distribute modified code is granted,
  10.  * provided the above notices are retained, and a notice that the code was
  11.  * modified is included with the above copyright notice.
  12.  *
  13.  * Author: Hans-J. Boehm (boehm@parc.xerox.com)
  14.  */
  15. /* Boehm, May 19, 1994 2:22 pm PDT */
  16.  
  17. /*
  18.  * Cords are immutable character strings.  A number of operations
  19.  * on long cords are much more efficient than their strings.h counterpart.
  20.  * In particular, concatenation takes constant time independent of the length
  21.  * of the arguments.  (Cords are represented as trees, with internal
  22.  * nodes representing concatenation and leaves consisting of either C
  23.  * strings or a functional description of the string.)
  24.  *
  25.  * The following are reasonable applications of cords.  They would perform
  26.  * unacceptably if C strings were used:
  27.  * - A compiler that produces assembly language output by repeatedly
  28.  *   concatenating instructions onto a cord representing the output file.
  29.  * - A text editor that converts the input file to a cord, and then
  30.  *   performs editing operations by producing a new cord representing
  31.  *   the file after echa character change (and keeping the old ones in an
  32.  *   edit history)
  33.  *
  34.  * For optimal performance, cords should be built by
  35.  * concatenating short sections.
  36.  * This interface is designed for maximum compatibility with C strings.
  37.  * ASCII NUL characters may be embedded in cords using CORD_from_fn.
  38.  * This is handled correctly, but CORD_to_char_star will produce a string
  39.  * with embedded NULs when given such a cord. 
  40.  */
  41. # ifndef CORD_H
  42.  
  43. # define CORD_H
  44. # include <stddef.h>
  45. # include <stdio.h>
  46. /* Cords have type const char *.  This is cheating quite a bit, and not    */
  47. /* 100% portable.  But it means that nonempty character string        */
  48. /* constants may be used as cords directly, provided the string is    */
  49. /* never modified in place.  The empty cord is represented by, and    */
  50. /* can be written as, 0.                        */
  51.  
  52. typedef const char * CORD;
  53.  
  54. /* An empty cord is always represented as nil     */
  55. # define CORD_EMPTY 0
  56.  
  57. /* Is a nonempty cord represented as a C string? */
  58. #define IS_STRING(s) (*(s) != '\0')
  59.  
  60. /* Concatenate two cords.  If the arguments are C strings, they may     */
  61. /* not be subsequently altered.                        */
  62. CORD CORD_cat(CORD x, CORD y);
  63.  
  64. /* Concatenate a cord and a C string with known length.  Except for the    */
  65. /* empty string case, this is a special case of CORD_cat.  Since the    */
  66. /* length is known, it can be faster.                    */
  67. CORD CORD_cat_char_star(CORD x, const char * y, size_t leny);
  68.  
  69. /* Compute the length of a cord */
  70. size_t CORD_len(CORD x);
  71.  
  72. /* Cords may be represented by functions defining the ith character */
  73. typedef char (* CORD_fn)(size_t i, void * client_data);
  74.  
  75. /* Turn a functional description into a cord.     */
  76. CORD CORD_from_fn(CORD_fn fn, void * client_data, size_t len);
  77.  
  78. /* Return the substring (subcord really) of x with length at most n,    */
  79. /* starting at position i.  (The initial character has position 0.)    */
  80. CORD CORD_substr(CORD x, size_t i, size_t n);
  81.  
  82. /* Return the argument, but rebalanced to allow more efficient       */
  83. /* character retrieval, substring operations, and comparisons.        */
  84. /* This is useful only for cords that were built using repeated     */
  85. /* concatenation.  Guarantees log time access to the result, unless    */
  86. /* x was obtained through a large number of repeated substring ops    */
  87. /* or the embedded functional descriptions take longer to evaluate.    */
  88. /* May reallocate significant parts of the cord.  The argument is not    */
  89. /* modified; only the result is balanced.                */
  90. CORD CORD_balance(CORD x);
  91.  
  92. /* The following traverse a cord by applying a function to each     */
  93. /* character.  This is occasionally appropriate, especially where    */
  94. /* speed is crucial.  But, since C doesn't have nested functions,    */
  95. /* clients of this sort of traversal are clumsy to write.  Consider    */
  96. /* the functions that operate on cord positions instead.        */
  97.  
  98. /* Function to iteratively apply to individual characters in cord.    */
  99. typedef int (* CORD_iter_fn)(char c, void * client_data);
  100.  
  101. /* Function to apply to substrings of a cord.  Each substring is a     */
  102. /* a C character string, not a general cord.                */
  103. typedef int (* CORD_batched_iter_fn)(const char * s, void * client_data);
  104. # define CORD_NO_FN ((CORD_batched_iter_fn)0)
  105.  
  106. /* Apply f1 to each character in the cord, in ascending order,        */
  107. /* starting at position i. If                        */
  108. /* f2 is not CORD_NO_FN, then multiple calls to f1 may be replaced by    */
  109. /* a single call to f2.  The parameter f2 is provided only to allow    */
  110. /* some optimization by the client.  This terminates when the right    */
  111. /* end of this string is reached, or when f1 or f2 return != 0.  In the    */
  112. /* latter case CORD_iter returns != 0.  Otherwise it returns 0.        */
  113. /* The specified value of i must be < CORD_len(x).            */
  114. int CORD_iter5(CORD x, size_t i, CORD_iter_fn f1,
  115.            CORD_batched_iter_fn f2, void * client_data);
  116.  
  117. /* A simpler version that starts at 0, and without f2:    */
  118. int CORD_iter(CORD x, CORD_iter_fn f1, void * client_data);
  119. # define CORD_iter(x, f1, cd) CORD_iter5(x, 0, f1, CORD_NO_FN, cd)
  120.  
  121. /* Similar to CORD_iter5, but end-to-beginning.    No provisions for    */
  122. /* CORD_batched_iter_fn.                        */
  123. int CORD_riter4(CORD x, size_t i, CORD_iter_fn f1, void * client_data);
  124.  
  125. /* A simpler version that starts at the end:    */
  126. int CORD_riter(CORD x, CORD_iter_fn f1, void * client_data);
  127.  
  128. /* Functions that operate on cord positions.  The easy way to traverse    */
  129. /* cords.  A cord position is logically a pair consisting of a cord    */
  130. /* and an index into that cord.  But it is much faster to retrieve a    */
  131. /* charcter based on a position than on an index.  Unfortunately,    */
  132. /* positions are big (order of a few 100 bytes), so allocate them with    */
  133. /* caution.                                */
  134. /* Things in cord_pos.h should be treated as opaque, except as        */
  135. /* described below.  Also note that                    */
  136. /* CORD_pos_fetch, CORD_next and CORD_prev have both macro and function    */
  137. /* definitions.  The former may evaluate their argument more than once. */
  138. # include "cord_pos.h"
  139.  
  140. /*
  141.     Visible definitions from above:
  142.     
  143.     typedef <OPAQUE but fairly big> CORD_pos[1];
  144.     
  145.     /* Extract the cord from a position:
  146.     CORD CORD_pos_to_cord(CORD_pos p);
  147.     
  148.     /* Extract the current index from a position:
  149.     size_t CORD_pos_to_index(CORD_pos p);
  150.     
  151.     /* Fetch the character located at the given position:
  152.     char CORD_pos_fetch(register CORD_pos p);
  153.     
  154.     /* Initialize the position to refer to the give cord and index.
  155.     /* Note that this is the most expensive function on positions:
  156.     void CORD_set_pos(CORD_pos p, CORD x, size_t i);
  157.     
  158.     /* Advance the position to the next character.
  159.     /* P must be initialized and valid.
  160.     /* Invalidates p if past end:
  161.     void CORD_next(CORD_pos p);
  162.     
  163.     /* Move the position to the preceding character.
  164.     /* P must be initialized and valid.
  165.     /* Invalidates p if past beginning:
  166.     void CORD_prev(CORD_pos p);
  167.     
  168.     /* Is the position valid, i.e. inside the cord?
  169.     int CORD_pos_valid(CORD_pos p);
  170. */
  171. # define CORD_FOR(pos, cord) \
  172.     for (CORD_set_pos(pos, cord, 0); CORD_pos_valid(pos); CORD_next(pos))
  173.  
  174.             
  175. /* An out of memory handler to call.  May be supplied by client.    */
  176. /* Must not return.                            */
  177. extern void (* CORD_oom_fn)(void);
  178.  
  179. /* Dump the representation of x to stdout in an implementation defined    */
  180. /* manner.  Intended for debugging only.                */
  181. void CORD_dump(CORD x);
  182.  
  183. /* The following could easily be implemented by the client.  They are    */
  184. /* provided in cord_xtra.c for convenience.                */
  185.  
  186. /* Concatenate a character to the end of a cord.    */
  187. CORD CORD_cat_char(CORD x, char c);
  188.  
  189. /* Return the character in CORD_substr(x, i, 1)      */
  190. char CORD_fetch(CORD x, size_t i);
  191.  
  192. /* Return < 0, 0, or > 0, depending on whether x < y, x = y, x > y    */
  193. int CORD_cmp(CORD x, CORD y);
  194.  
  195. /* A generalization that takes both starting positions for the         */
  196. /* comparison, and a limit on the number of characters to be compared.    */
  197. int CORD_ncmp(CORD x, size_t x_start, CORD y, size_t y_start, size_t len);
  198.  
  199. /* Find the first occurrence of s in x at position start or later.    */
  200. /* Return the position of the first character of s in x, or        */
  201. /* CORD_NOT_FOUND if there is none.                    */
  202. size_t CORD_str(CORD x, size_t start, CORD s);
  203.  
  204. /* Return a cord consisting of i copies of (possibly NUL) c.  Dangerous    */
  205. /* in conjunction with CORD_to_char_star.                */
  206. /* The resulting representation takes constant space, independent of i.    */
  207. CORD CORD_chars(char c, size_t i);
  208. # define CORD_nul(i) CORD_chars('\0', (i))
  209.  
  210. /* Turn a file into cord.  The file must be seekable.  Its contents    */
  211. /* must remain constant.  The file may be accessed as an immediate    */
  212. /* result of this call and/or as a result of subsequent accesses to     */
  213. /* the cord.  Short files are likely to be immediately read, but    */
  214. /* long files are likely to be read on demand, possibly relying on     */
  215. /* stdio for buffering.                            */
  216. /* We must have exclusive access to the descriptor f, i.e. we may    */
  217. /* read it at any time, and expect the file pointer to be        */
  218. /* where we left it.  Normally this should be invoked as        */
  219. /* CORD_from_file(fopen(...))                        */
  220. /* CORD_from_file arranges to close the file descriptor when it is no    */
  221. /* longer needed (e.g. when the result becomes inaccessible).        */ 
  222. /* The file f must be such that ftell reflects the actual character    */
  223. /* position in the file, i.e. the number of characters that can be     */
  224. /* or were read with fread.  On UNIX systems this is always true.  On    */
  225. /* MS Windows systems, f must be opened in binary mode.            */
  226. CORD CORD_from_file(FILE * f);
  227.  
  228. /* Equivalent to the above, except that the entire file will be read    */
  229. /* and the file pointer will be closed immediately.            */
  230. /* The binary mode restriction from above does not apply.        */
  231. CORD CORD_from_file_eager(FILE * f);
  232.  
  233. /* Equivalent to the above, except that the file will be read on demand.*/
  234. /* The binary mode restriction applies.                    */
  235. CORD CORD_from_file_lazy(FILE * f);
  236.  
  237. /* Turn a cord into a C string.    The result shares no structure with    */
  238. /* x, and is thus modifiable.                        */
  239. char * CORD_to_char_star(CORD x);
  240.  
  241. /* Write a cord to a file, starting at the current position.  No    */
  242. /* trailing NULs are newlines are added.                */
  243. /* Returns EOF if a write error occurs, 1 otherwise.            */
  244. int CORD_put(CORD x, FILE * f);
  245.  
  246. /* "Not found" result for the following two functions.            */
  247. # define CORD_NOT_FOUND ((size_t)(-1))
  248.  
  249. /* A vague analog of strchr.  Returns the position (an integer, not    */
  250. /* a pointer) of the first occurrence of (char) c inside x at position     */
  251. /* i or later. The value i must be < CORD_len(x).            */
  252. size_t CORD_chr(CORD x, size_t i, int c);
  253.  
  254. /* A vague analog of strrchr.  Returns index of the last occurrence    */
  255. /* of (char) c inside x at position i or earlier. The value i        */
  256. /* must be < CORD_len(x).                        */
  257. size_t CORD_rchr(CORD x, size_t i, int c);
  258.  
  259.  
  260. /* The following are also not primitive, but are implemented in     */
  261. /* cordprnt.c.  They provide functionality similar to the ANSI C    */
  262. /* functions with corresponding names, but with the following        */
  263. /* additions and changes:                        */
  264. /* 1. A %r conversion specification specifies a CORD argument.  Field    */
  265. /*    width, precision, etc. have the same semantics as for %s.        */
  266. /*    (Note that %c,%C, and %S were already taken.)            */
  267. /* 2. The format string is represented as a CORD.                */
  268. /* 3. CORD_sprintf and CORD_vsprintf assign the result through the 1st    */     /*    argument.    Unlike their ANSI C versions, there is no need to guess    */
  269. /*    the correct buffer size.                        */
  270. /* 4. Most of the conversions are implement through the native         */
  271. /*    vsprintf.  Hence they are usually no faster, and             */
  272. /*    idiosyncracies of the native printf are preserved.  However,    */
  273. /*    CORD arguments to CORD_sprintf and CORD_vsprintf are NOT copied;    */
  274. /*    the result shares the original structure.  This may make them    */
  275. /*    very efficient in some unusual applications.            */
  276. /*    The format string is copied.                    */
  277. /* All functions return the number of characters generated or -1 on    */
  278. /* error.  This complies with the ANSI standard, but is inconsistent    */
  279. /* with some older implementations of sprintf.                */
  280.  
  281. /* The implementation of these is probably less portable than the rest    */
  282. /* of this package.                            */
  283.  
  284. #ifndef CORD_NO_IO
  285.  
  286. #include <stdarg.h>
  287.  
  288. int CORD_sprintf(CORD * out, CORD format, ...);
  289. int CORD_vsprintf(CORD * out, CORD format, va_list args);
  290. int CORD_fprintf(FILE * f, CORD format, ...);
  291. int CORD_vfprintf(FILE * f, CORD format, va_list args);
  292. int CORD_printf(CORD format, ...);
  293. int CORD_vprintf(CORD format, va_list args);
  294.  
  295. #endif /* CORD_NO_IO */
  296.  
  297. # endif /* CORD_H */
  298.